;; solve_15_puzzle
;; license: http://code.google.com/p/jc-pheap/source/browse/trunk/jc-pheap/license.txt

(ns clj-algorithms.solve-15-puzzle
  (:require [clj-algorithms.a-star :as a-star]))

(defn score-state-simple [user-state goal-state]
   (loop [error-count 0
          user-s (first user-state)
          goal-s (first goal-state)]
       (if (seq goal-s)
           (if (not= (first user-s) (first goal-s))
               (recur (+ error-count 1) (next user-s) (next goal-s))
               (recur error-count (next user-s) (next goal-s)))
           error-count)))
           
;; computes sum of Manhattan distances
;; not really necessary for 15 puzzle.  simple heuristic works ok.
(defn score-state [user-state goal-state]
   (loop [error-count 0
          user-s (first user-state)
          goal-s (first goal-state)]
       (if (seq goal-s)
          (let [u (read-string (first user-s))
                g (read-string (first goal-s))
                up-down-moves
                      (Math/abs (- (int (Math/ceil (/ u 4)))
                                   (int (Math/ceil (/ g 4)))))
                left-right-moves
                      (Math/abs (- (let [a (mod u 4)] (if (= 0 a) 4 a))
                                   (let [a (mod g 4)] (if (= 0 a) 4 a))))]
             (recur (+ error-count up-down-moves left-right-moves) (next user-s) (next goal-s)))
          error-count)))
           
(defn print-history [history]
   (doseq [i history]
      (prn i)))

; belongs in basic stuff, next to its inverse, 'nth'?
(defn pos [coll item] (.indexOf (seq coll) item))
 
(defn exchange [state pos1 pos2]
     (if (or (< pos2 0) (> pos2 15))
       nil
       (assoc state pos1 (state pos2) pos2 (state pos1) )))

(let [already-tried (atom (hash-set))]
  (defn add-if-new [history new-state]
     (if (or (.contains history new-state)
             (.contains @already-tried new-state)) 
        nil
        (do
          (swap! already-tried conj new-state)
          (conj history new-state)))))
       
(defn get-transitions [history]
;; return vector of alternatives to try from here
   (let [state (first history)
         p (pos state "16")
         option1 (add-if-new history (exchange state p (inc p)))
         option2 (add-if-new history (exchange state p (dec p)))
         option3 (add-if-new history (exchange state p (+ p 4)))
         option4 (add-if-new history (exchange state p (- p 4)))]
    (cond
       (= p 0) (vec (remove nil?  [option1 option3]))
       (= p 3) (vec (remove nil?  [option2 option3]))
       (= p 12) (vec (remove nil? [option1 option4]))
       (= p 15) (vec (remove nil? [option2 option4]))
       (< p 3) (vec (remove nil?  [option1 option2 option3]))
       (> p 12) (vec (remove nil? [option1 option2 option4]))
       (or (= p 4) (= p 8)) (vec (remove nil?  [option1 option3 option4]))
       (or (= p 7) (= p 11)) (vec (remove nil? [option2 option3 option4]))
       :else (vec (remove nil? [option1 option2 option3 option4])))))

(a-star/a-star '(["9" "2" "12" "6"
                  "5" "7" "14" "13"
                  "3" "4" "1" "11"
                  "15" "10" "8" "16"])
               '(["1" "2" "3" "4"
                  "5" "6" "7" "8"
                  "9" "10" "11" "12"
                  "13" "14" "15" "16"])
               score-state-simple get-transitions print-history)
